package 数据结构和算法入门计划8月开始;
// 困难的打扰了
public class 数字1的个数330820 {
    // class Solution {
//     public int countDigitOne(int n) {
//         int ans = 0;
//         for (int i = 1; i <= n; i++) {
//             int count = 0;
//             int num = i;
//             while (num != 0) {
//                 // 从个位数开始一位一位的和1比较
//                 if (num % 10 == 1) {
//                     count++;
//                 }
//                 num /= 10;
//             }
//             ans += count;
//         }
//         return ans;
//     }
// }

    class Solution {
        public int countDigitOne(int n) {
            // 2021
            int ans = 0;
            for (int i = 1; i <= n; i *= 10) {
                ans += (n / (i * 10)) * i + Math.min(Math.max(n % (i * 10) - i + 1,0), i);
            }
            return ans;
        }
    }


}
